package structure;
import java.util.*;

public class Test1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

    }
    //leetcode 92.反转链表 Ⅱ(新方法)
    class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if (head == null || head.next == null || m == n) {
                return head;
            }
            int left = 1;
            ListNode cur = head;
            // 用于保存左边缘结点的前一位
            ListNode lcur = null;
            // 用于保存左边缘结点
            ListNode Lcur = null;
            while (cur != null && left != m) {
                //获取左边缘结点的前一位
                if (left == m - 1) {
                    lcur = cur;
                }
                cur = cur.next;
                left++;
            }
            //获取左边缘结点
            Lcur = cur;
            ListNode curn = cur.next;
            while (curn != null && left != n) {
                ListNode curN = curn.next;
                curn.next = cur;
                cur = curn;
                curn = curN;
                left++;
            }
            if(m == 1 && curn != null){
                head.next = curn;
            }else if(m != 1 && curn == null){
                lcur.next = cur;
                Lcur.next = null;
            }else if(m != 1 && curn != null){
                lcur.next = cur;
                Lcur.next = curn;
            }else{
                Lcur.next = null;
            }
            if(m != 1){
                return head;
            }
            return cur;
        }
    }
    //leetcode 86.分隔链表
    class Solution0 {
        public ListNode partition(ListNode head, int x) {
            ListNode left = new ListNode(), pl = left;
            ListNode right = new ListNode(), pr = right;
            while(head != null){
                if(head.val < x){
                    pl.next = head;
                    pl = pl.next;
                }else{
                    pr.next = head;
                    pr = pr.next;
                }
                head = head.next;
            }
            pr.next = null;
            pl.next = right.next;
            return left.next;
        }
    }
}

